#include <iostream>
#include <cmath>
#include <cstring>

int recurveCut(int n, const int* price, int p_num)
{
  int sum = 0;
  if (n > p_num) {
    sum = recurveCut(p_num, price, p_num) + recurveCut(n - p_num, price, p_num);
  } else {
    for (int i = 1; i <= n; ++i) {
      sum = std::max(sum, price[i] + recurveCut(n - i, price, p_num));
    }
  }
  return sum;
}

int memoCut(int n, int* profit, const int* price, int p_num)
{
  int sum = 0;
  if (n > p_num) {
    sum = memoCut(p_num, profit, price, p_num) + memoCut(n - p_num, profit, price, p_num);
  } else {
    if (profit[n] == 0) {
      for (int i = 1; i <= n; ++i) {
        profit[n] = std::max(profit[n], price[i] + memoCut(n - i, profit, price, p_num));
      }
    }

    sum = profit[n];
  }

  return sum;
}

int dynamicCut(int n, int* profit, const int* price, int p_num)
{
  int sum = 0;
  if (n > p_num) {
    sum = dynamicCut(p_num, profit, price, p_num) + dynamicCut(n - p_num, profit, price, p_num);
  } else {
    if (profit[n] == 0) {
      for (int i = 1; i <= n; ++i) {
        int flag = 1;  // 记录钢条长度为i时应先切割的整段长度为多少
        
        for (int j = 1; j <= i; ++j) {
          int p_j = price[j] + profit[i - j];
          if (p_j > profit[i]) {
            flag = j;
            profit[i] = p_j;
          }
        }

        std::cout << i << "\tchoose\t" << flag << std::endl;
      }
    }

    sum = profit[n];
  }

  return sum;
}

int main(int argc, char* argv[])
{
  if (argc != 2) {
    std::cout << "Param error!" << std::endl;
    return -1;
  }
  int n = atoi(argv[1]);  // 待切割的钢条总长度

  int price[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
  int p_num = sizeof(price) / sizeof(price[0]) - 1;

  // 递归方式切割钢条
  std::cout << recurveCut(n, price, p_num) << std::endl;
  
  // 备忘录方式切割钢条
  int* profit = (int*)calloc(p_num + 1, sizeof(int));
  if (profit == nullptr) {
    return -1;
  }
  std::cout << memoCut(n, profit, price, p_num) << std::endl;

  // 动态规划方式切割钢条
  memset(profit, 0, (p_num + 1) * sizeof(int));
  std::cout << dynamicCut(n, profit, price, p_num) << std::endl;
  free(profit);

  return 0;
}

